package Demo31;

import java.util.HashMap;

/**
 * 和可被K整除的子数组
 * https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
 * 我们这里采用的是 前缀和 + hash表
 * 这里用到了两个知识点
 * 1. 同余定理
 *      (a-b) / p = k 余0 => a % p = b % p
 * 2. 负数 % 整数 的结果以及修正
 *      结论 : (a % k + k) % k    k 为被除数
 *      用这个公式,不管 被除数是正数还是负数我们都可以得到 正余数
 */

class Solution {
    /**
     * 这里创建一个 整型数组来代替我们的HashMap 减少开销
     * 数组长度只需要 k 因为 我们存放的是余数
     * @param nums
     * @param k
     * @return
     */
    public int subarraysDivByK(int[] nums, int k) {
        int[] hash = new int[k];
        hash[0] = 1;

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int key = (sum % k + k) % k;
            ret += hash[key];
            hash[key]++;
        }
        return ret;
    }

    /**
     * 这里采用hashMap 来统计
     * @param nums
     * @param k
     * @return
     */
    public int subarraysDivByK1(int[] nums, int k) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            ret += hash.getOrDefault((sum % k + k)%k,0);
            hash.put((sum % k + k) % k,hash.getOrDefault((sum % k + k) % k,0) + 1);
        }
        return ret;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.subarraysDivByK(new int[] {4,5,0,-2,-3,1},5);
        System.out.println(ret);
    }
}